/*
**  P88
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct PolyNode {
    int coef;
    int expon;
    struct PolyNode* link;
}* Polynomial;

int Compare ( int e1, int e2 );

void Attach ( int coef, int expon, Polynomial* PtrRear );

Polynomial PolyAdd ( Polynomial P1, Polynomial P2 );

int main() {
    Polynomial P1, P2, rear, P3, out;
    int N, cnt = 1;
    printf("Please input the number of the terms in P1\n");
    scanf("%d",&N);
    printf("Please input P1, like 3x^3+1x^1\n");
    P1 = (Polynomial)malloc(sizeof(struct PolyNode));
    scanf("%dx^%d",&P1->coef, &P1->expon);
    P1->link = NULL;
    rear = P1;
    while( cnt < N) {
        Polynomial tmp;
        tmp = (Polynomial)malloc(sizeof(struct PolyNode));
        scanf("%dx^%d",&tmp->coef, &tmp->expon);
        tmp->link = NULL;
        rear->link = tmp;
        rear = tmp;
        cnt++;
    }
    printf("Please input the number of the terms in P2\n");
    scanf("%d",&N);
    printf("Please input P2, like 3x^3+1x^1\n");
    P2 = (Polynomial)malloc(sizeof(struct PolyNode));
    scanf("%dx^%d",&P2->coef, &P2->expon);
    P2->link = NULL;
    rear = P2;
    cnt = 1;
    while( cnt < N) {
        Polynomial tmp;
        tmp = (Polynomial)malloc(sizeof(struct PolyNode));
        scanf("%dx^%d",&tmp->coef, &tmp->expon);
        tmp->link = NULL;
        rear->link = tmp;
        rear = tmp;
        cnt++;
    }

    P3 = PolyAdd(P1,P2);
    cnt = 1;
    if (P3) {
        printf("%dx^%d",P3->coef,P3->expon);
        P3 = P3->link;
    }
    while(P3) {
        if ( P3->coef > 0 ) printf("+");
        printf("%dx^%d",P3->coef,P3->expon);
        out = P3;
        P3 = P3->link;
        free(out);
        
    }
    while(P2) {
        out = P2;
        P2 = P2->link;
        free(out);
    }
    while(P1) {
        out = P1;
        P1 = P1->link;
        free(out);
    }
    return 0;
}

int Compare ( int e1, int e2 ) {
    if ( e1 > e2 ) return 1;
    else if ( e1 < e2 ) return -1;
    else return 0;
}

void Attach ( int coef, int expon, Polynomial* PtrRear ) {
    Polynomial P;

    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = coef;
    P->expon = expon;
    P->link = NULL;
    (*PtrRear)->link = P;
    *PtrRear = P;
}

Polynomial PolyAdd ( Polynomial P1, Polynomial P2 ) {
    Polynomial front, rear, temp;
    int sum;
    rear = (Polynomial)malloc(sizeof(struct PolyNode));
    front = rear;
    while ( P1 && P2 )
        switch ( Compare(P1->expon, P2->expon) ) {
            case 1:
                Attach(P1->coef, P1->expon, &rear);
                P1 = P1->link;
                break;
            case -1:
                Attach(P2->coef, P2->expon, &rear);
                P2 = P2->link;
                break;
            case 0:
                sum = P1->coef + P2->coef;
                if (sum) Attach(sum, P1->expon, &rear);
                P1 = P1->link;
                P2 = P2->link;
                break;
        }
    for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
    for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear);
    rear->link = NULL;
    temp = front;
    front = front->link;
    free(temp);
    return front;
}